package leetcode_1601_1700;

public class LeeCode_1626_failed {
    public static void main(String[] args) {
        System.out.println(bestTeamScore(new int[]{1, 3, 5, 10, 15}, new int[]{1, 2, 3, 4, 5}));
        System.out.println(bestTeamScore(new int[]{4,5,6,5}, new int[]{2,1,2,1}));
        System.out.println(bestTeamScore(new int[]{1,2,3,5}, new int[]{8,9,10,1}));
        System.out.println(bestTeamScore(new int[]{1,1,1,1,1,1,1,1,1,1},
                new int[]{811,364,124,873,790,656,581,446,885,134}));
    }
    private static int bestTeamScore(int[] scores, int[] ages) {
        int m = ages.length;
        sort2(scores, ages, 0, m - 1);
        int[] max = new int[1];
        f(scores, ages, 0, 0, 0, max);
        return max[0];
    }
    private static void f(int[] scores, int[] ages, int i, int b, int sum, int[] max){
        if (i == ages.length){
            max[0] = Math.max(sum, max[0]);
            return;
        }
        if (i == ages.length - 1){
            if (scores[i] == scores[b] || ages[i] >= ages[b]){
                sum += scores[i];
                max[0] = Math.max(max[0], sum);
                return;
            }else {
                max[0] = Math.max(max[0], sum);
                return;
            }
        }
        if (ages[i] > ages[i + 1] && scores[i] < scores[i + 1]){
            f(scores, ages, i + 1, b, sum, max);
            int i2 = i;
            while (i2 < ages.length && ages[i2] <= ages[i]){
                i2++;
            }
            f(scores, ages, i2, b, sum + scores[i], max);
        }else {
            f(scores, ages, i + 1, b, sum + scores[i], max);
        }
    }

    private static void sort2(int[] score, int[] ages, int l, int r){
        if (l >= r)
            return;
        int start = l;
        int end = r;
        int basNum = score[l];
        while (l < r){
            while (l < r && score[r] >= basNum){
                r--;
            }
            while (l < r && score[l] <= basNum){
                l++;
            }
            if (l == r)
                break;
            int tmp = score[l];
            score[l] = score[r];
            score[r] = tmp;
            tmp = ages[l];
            ages[l] = ages[r];
            ages[r] = tmp;
        }
        score[start] = score[l];
        score[l] = basNum;
        int tmp = ages[start];
        ages[start] = ages[l];
        ages[l] = tmp;
        sort2(score, ages, start, l - 1);
        sort2(score, ages, l + 1, end);
    }
}
